package Z.dailyExercise.holiday;

public class _441_排列硬币 {
    public static void main(String[] args) {
        _441_排列硬币 test = new _441_排列硬币();
        System.out.println(test.arrangeCoins(1804289383));
    }
    /**
     *
     * @param n
     * @return
     */
    public int arrangeCoins(int n) {

        if (n==0){
            return 0;
        }
        return helper(n,1,n);

    }
    public int helper(int n,long low,long high){
        if (low>high){
            return -1;
        }
        long mid = low+(high-low)/2;
        long count = (1+mid)*mid/2;

        if (count==n){
            return (int) mid;
        }else if (count<n){
            if ((count+mid+1)>n){
                return (int) mid;
            }else{
                return helper(n,mid+1,high);
            }
        }else {
            if (mid*(mid-1)/2 < n){
                return (int) mid-1;
            }else {
                return helper(n,low,mid-1);
            }
        }

    }

}
